//
// Created by cljh on 2023/3/28.
//

#ifndef BIN_PACKING_GENETICALGORITHM_H
#define BIN_PACKING_GENETICALGORITHM_H


#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include "../entity/Individual.h"
#include "../entity/NestPath.h"
#include "../utils/ClipperUtil.h"
#include <unordered_set>

class GeneticAlgorithm{
public:
    std::vector<Individual*> population;//需要在函数中修改Individual的适应度，同时在迭代的时候创建与销毁个体
    int populationSize;
    double mutateRate;
    int angleScale;//旋转角度 设置为2，意味着可以旋转0，180； 4即可以旋转0，90，180，270
    std::mt19937 rng_; // 随机数生成器对象
    std::uniform_real_distribution<double> rand_double;  // [0,1)

    GeneticAlgorithm(int _populationSize,double  _mutateRate,int _angleScale){
        populationSize=_populationSize;
        mutateRate=_mutateRate;
        angleScale=_angleScale;
        rand_double = std::uniform_real_distribution<double>(0.0, 1.0);
        rng_ = std::mt19937(std::chrono::system_clock::now().time_since_epoch().count());
        //        rng_ = std::mt19937(1684158932698592100);
        std::cout<<"rng_ = "<<std::chrono::system_clock::now().time_since_epoch().count()<<std::endl;
        //        population = nullptr;
    }
    ~GeneticAlgorithm(){
        for(Individual* individual:population){
            delete individual;
        }
    }

    static bool cmp(NestPath a,NestPath b){ // 由大到小
        return a.area>b.area;
    }

    void initPopulation(std::vector<NestPath>& parts){
        std::vector<Individual*> _population;
        //按照面积排序
        std::sort(parts.begin(),parts.end(),cmp);

        Individual *individual= new Individual(parts);
        _population.push_back(individual);

        while (_population.size()<populationSize){
            Individual *mutant = mutate(_population[0]);
            _population.push_back(mutant);
        }
        population=_population;
    }

    Individual* mutate_svgnest(const Individual* individual) {
        std::vector<NestPath> newPaths = individual->paths;
        std::uniform_int_distribution<int> rand_int(0, newPaths.size()-1); //[0, newPaths.size()-1]

        for (int i = 0; i < newPaths.size(); i++) {
            double randomNum = rand_double(rng_);
            if (randomNum < mutateRate) {
                int j = i+1;
                if(j<newPaths.size()){
                    std::swap(newPaths[i], newPaths[j]);
                }
            }
            randomNum = rand_double(rng_);
            //TODO:加上对角度的合理性判断
            if (randomNum < mutateRate) {
                newPaths[i].rotation = randomAngle();
            }
        }
        return new Individual(newPaths);
    }

    // 变异函数 交换位置
    Individual* mutate_swap(const Individual* individual) {
        std::vector<NestPath> newPaths = individual->paths;
        std::uniform_int_distribution<int> rand_int(0, newPaths.size()-1); //[0, newPaths.size()-1]

        for (int i = 0; i < newPaths.size(); i++) {
            double randomNum = rand_double(rng_);
            if (randomNum < mutateRate) {
                int j = rand_int(rng_);
                std::swap(newPaths[i], newPaths[j]);
            }
            randomNum = rand_double(rng_);
            //TODO:加上对角度的合理性判断
            if (randomNum < mutateRate) {
                newPaths[i].rotation = randomAngle();
            }
        }
        return new Individual(newPaths);
    }

    // 变异函数 将 paths[j] 插入到 paths[i] 前面
    Individual* mutate_insert(const Individual* individual) {
        std::vector<NestPath> newPaths = individual->paths;
        std::uniform_int_distribution<int> rand_int(0, newPaths.size()-1); //[0, newPaths.size()-1]

        for (int i = 0; i < newPaths.size(); i++) {
            double randomNum = rand_double(rng_);
            if (randomNum < mutateRate) {
                int j = rand_int(rng_);
                while (j == i)
                    j = rand_int(rng_);
                NestPath tmp=newPaths[j];
                newPaths.erase(newPaths.begin()+j);
                newPaths.insert(newPaths.begin()+i, tmp);
            }
            randomNum = rand_double(rng_);
            //TODO:加上对角度的合理性判断
            if (randomNum < mutateRate) {
                newPaths[i].rotation = randomAngle();
            }
        }
        return new Individual(newPaths);
    }

    // 变异函数 随机翻转一段序列
    Individual* mutate_reverse(const Individual* individual) {
        std::vector<NestPath> newPaths = individual->paths;
        std::uniform_int_distribution<int> rand_int(0, newPaths.size()-1); //[0, newPaths.size()-1]
        int pos1 = rand_int(rng_);
        int pos2 = rand_int(rng_);
        // 确保 pos1 < pos2
        if (pos1 > pos2) {
            std::swap(pos1, pos2);
        }
        // 翻转 pos1 和 pos2 之间的元素
        std::reverse(newPaths.begin() + pos1, newPaths.begin() + pos2 + 1);

        return new Individual(newPaths);
    }

    enum MutateType {
        Swap,
        Insert,
        Reverse
    };

    Individual* mutate(const Individual* individual) {
        // 随机选择一个变异函数类型
        int type = static_cast<MutateType>(rand_double(rng_) * 2);  // 类型转换static_cast
//        switch (type) {
//        case Swap:
//            return mutate_svgnest(individual);
//        case Insert:
//            return mutate_insert(individual);
//        case Reverse:
//            return mutate_reverse(individual);
//        }
//        std::cout<<R"(error in "mutate" of "Individual" )";
//        return nullptr;
        return mutate_svgnest(individual);
    }


    void generation(){
        std::vector<Individual*> newpopulation;
        //        newpopulation->push_back(population->at(0));
        while (newpopulation.size() < populationSize) {
            // 选择+交叉
            Individual* male = randomWeightedIndividual(nullptr);
            Individual* female = randomWeightedIndividual(male);
            if (male == nullptr|| female == nullptr){
                std::cout<<"mate went wrong"<<std::endl;
            }
            std::vector<Individual*> children = mate(male, female);
            // 变异
            newpopulation.push_back(mutate(children[0]));
            if (newpopulation.size() < population.size()) {
                newpopulation.push_back(mutate(children[1]));
            }
        }
        //        delete population;
        for(Individual* individual:population){
            delete individual;
        }
        population = newpopulation;
    }
    /**
     * 交叉
     * @param male
     * @param female
     * @return
     */
    std::vector<Individual*> mate(Individual* male, Individual* female) {
        if(male== nullptr||female== nullptr){
            std::cout<<"wrong in mate";
        }
        std::vector<Individual*> children;
        double randnum = rand_double(rng_); // [0-1)
        //        std::cout<< "mate";
        int cutpoint = round(fmin(fmax(randnum, 0.1), 0.9) * (male->size() - 1)); // 交叉断点（0.1 ~ 0.9）
        //        std::cout<<"cutpoint: "<<cutpoint<<std::endl;

        std::vector<NestPath> gene1;  // 裁片
        std::vector<NestPath> gene2;

        // 记录子代中已有的元素
        std::unordered_set<int> placed1;
        std::unordered_set<int> placed2;

        // 首先将交叉断点之前的基因直接复制到子代中
        for (int i = 0; i < cutpoint; i++) {
            gene1.emplace_back(male->getPath(i));
            placed1.insert(gene1[i].id);

            gene2.emplace_back(female->getPath(i));
            placed2.insert(gene2[i].id);
        }


        for (int i = 0; i < male->size(); i++) {
            if (!placed1.count(female->getPath(i).id)) {
                gene1.emplace_back(female->getPath(i));
                placed1.insert(female->getPath(i).id);
            }
        }
        for (int j = 0; j < female->size(); j++) {
            if (!placed2.count(male->getPath(j).id)) {
                gene2.emplace_back(male->getPath(j));
                placed2.insert(male->getPath(j).id);
            }
        }
        //        cout<<cutpoint<<endl;

        Individual *individual1 = new Individual(gene1);
        Individual *individual2 = new Individual(gene2);
        //TODO:检查是否超过边界

        children.push_back(individual1);
        children.push_back(individual2);

        return children;
    }

    /**
    * 从population中产生一个随机新个体，轮盘赌
    * @param exclude 如果有，则随机选择除了exclude的个体
    * @return
    */
    Individual* randomWeightedIndividual(Individual* exclude){
        std::vector<Individual*> pop=std::vector<Individual*>();
        double totalFitness = 0;
        if (population.empty()){
            std::cout<<"wrong";
            return nullptr;
        }
        for(int i=0;i<population.size();i++){
            Individual * individual=population[i];
            pop.emplace_back(individual);
            totalFitness += individual->getFitness();
        }
        if (exclude != nullptr) {
            auto iter=find(pop.begin(), pop.end(), exclude);
            if (iter!=pop.end()) {
                //                std::cout<<"finded"<<std::endl;
                pop.erase(iter);
                totalFitness -= exclude->getFitness();
            }else{
                std::cout<<"error in selecting individual!!!";
            }
        }
        double randnum = rand_double(rng_);
        //        std::cout<<"randnum: "<<randnum<<std::endl;

        // Select an individual using roulette wheel selection
        double cumulativeFitness = 0;
        Individual *selected = nullptr;
        for (auto& individual : pop) {
            cumulativeFitness += individual->getFitness() / totalFitness;
            if (cumulativeFitness >= randnum) {
                selected = individual;
            }
        }

//        std::cout<<"wrong in randomWeightedIndividual"<<std::endl;
        return selected;
    }
    int randomAngle(){
        std::uniform_int_distribution<int> rand_int(0, angleScale-1); //[0, angleScale-1]
        int randAngle=(360.0/angleScale)*(rand_int(rng_));
        //        std::cout<<"randomangle: "<<randAngle<<std::endl;
        return randAngle;
    }

    friend std::ostream &operator<<(std::ostream &os, GeneticAlgorithm &ga);
};

//std::ostream &operator<<(std::ostream &os, GeneticAlgorithm &ga){
//    os << "ga: ";
//    int count = 0;
//    for (int i = 0; i < ga.populationSize; i++) {
//        os << "Individual " + std::to_string(count) + ":\n";
//        count++;
//        os << ga.population[i];
//    }
//    return os;
//}



#endif //BIN_PACKING_GENETICALGORITHM_H
